Three Sum
LC109:找linked list中间值
判断linked list成环
Move Inside an Array Or maybe can solve by DP
LC489. Robot Room Cleaner
iterator的DFS,需要一个stack和一个visited
递归的思想:要么简化成若干个子问题,要么直接解决问题
recursion验证,对于可以递归定义的题,可以recursion
LC333. Largest BST Subtree
另外比如检查树是不是对称的,需要两个pointer来recursion
遇到需要先后次序的题,考虑建图然后Topological sort
LC444. Sequence Reconstruction
Input:
1 5 6
4 3 2
8 7 9
Output:
1 3 4
3 2 1
5 4 6
LC23 Merge k Sorted Lists
DP的理解
two attribute for DP problem
optimal substructure: the optimal solution can be obtained by combination of optimal solutions to sub-problems
如果只有这一个条件,就是divide and conquer/recursive
overlapping sub-problems
the sub-problem will be solved more than once
两种方法
思考DP方程的时候有两种方法;
LC403. Frog Jump
DP可以看作是DFS的改进,思考的时候可以先从DFS开始,然后找overlap sub-problem
对于搜索空间很大时,DP不一定是vector,也可以是map
尤其是题目对搜索空间有限制的时候,更可能是DP
经典DP寻路,如果是DP需要上面和左边的点的信息,只需要先行后列遍历即可
LC410. Split Array Largest Sum
DP方程不一定都从其他方程推出来,也可以结合输入
LC552. Student Attendance Record II
类似一个数学问题,考虑能不能递推(利用上一次的信息)
LC rain water
prefix tree和hash table的区别就是prefix tree可以支持start_with查询
一样的地方在于都可以insert/find/remove
Two Sum
Word Search II
报数问题
Sliding Window Maximum:Deque
实现一个带tag的queue,push的时候有tag,pop的时候可以指定tag,也可以不指定
Merge Interval
LC240. Search a 2D Matrix II
直接可以排除一行或者一列
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
求下一个排列
找按数字顺序递增,且比当前数字小,且尽量大的数字
12332 -> 12299
LC680. Valid Palindrome II
可以直接从外向内检查
LC1216. Valid Palindrome III
是LC680的变种,可以greedy检查,然后DFS
对于一个有序数组,其中一个数字出现了一次,其他都出现了两次,求出现一次数字的位置
划分数组使得子数列的和的最大值最小
LC410. Split Array Largest Sum
在答案域上binary search,如果能快速验证
Binary search也可以用来确认一个数组的结尾在哪里
比如一个大小为N的数组,前k个都是1,其余是0,找k
可以用binary search去找最后一个1
binary search的本质不在于找到某一个确定的点,本质在于可以每次排除一半的可能
Complete tree上的binary search,每次寻址logN,所以是O(log^2N)
比如
LC222. Count Complete Tree Nodes
同类型的题还有在complete tree上每一行都是有序的,查找某一个值,也是在一层上binary search
在写binary search的时候,一定保证每次都能缩小范围,比如l = med+1, r= med-1,防止死循环
Tarjan LCA
注意,general的LCA应该是一个map from ElementType to SetType
google rain
对于数字范围很小的情况,考虑bucket
LC1057. Campus Bikes
因为distance是0~2000,所以可以考虑用bucket sort代替heap sort
对于N个元素,找前k个,就是O(Nlogk)
但是如果可以落在M个bucket里面,那么就是O(M+N)
Sliding Window Median,加上条件数字都在M范围内,那么也可以用bucket